Search Results

Documents authored by Zwicker, William S.

Document
DOI: 10.4230/LIPIcs.ITCS.2019.14
Almost Envy-Free Allocations with Connected Bundles

Authors: Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph G. When the items are arranged in a path, we show that EF1 allocations are guaranteed to exist for arbitrary monotonic utility functions over bundles, provided that either there are at most four agents, or there are any number of agents but they all have identical utility functions. Our existence proofs are based on classical arguments from the divisible cake-cutting setting, and involve discrete analogues of cut-and-choose, of Stromquist's moving-knife protocol, and of the Su-Simmons argument based on Sperner's lemma. Sperner's lemma can also be used to show that on a path, an EF2 allocation exists for any number of agents. Except for the results using Sperner's lemma, all of our procedures can be implemented by efficient algorithms. Our positive results for paths imply the existence of connected EF1 or EF2 allocations whenever G is traceable, i.e., contains a Hamiltonian path. For the case of two agents, we completely characterize the class of graphs G that guarantee the existence of EF1 allocations as the class of graphs whose biconnected components are arranged in a path. This class is strictly larger than the class of traceable graphs; one can check in linear time whether a graph belongs to this class, and if so return an EF1 allocation.
Cite as

Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. Almost Envy-Free Allocations with Connected Bundles. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ITCS.2019.14,
  author =	{Bil\`{o}, Vittorio and Caragiannis, Ioannis and Flammini, Michele and Igarashi, Ayumi and Monaco, Gianpiero and Peters, Dominik and Vinci, Cosimo and Zwicker, William S.},
  title =	{{Almost Envy-Free Allocations with Connected Bundles}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.14},
  URN =		{urn:nbn:de:0030-drops-101078},
  doi =		{10.4230/LIPIcs.ITCS.2019.14},
  annote =	{Keywords: Envy-free Division, Cake-cutting, Resource Allocation, Algorithmic Game Theory}
}
Document
DOI: 10.4230/DagSemProc.10101.1
10101 Abstracts Collection – Computational Foundations of Social Choice

Authors: Felix Brandt, Vincent Conitzer, Lane A. Hemaspaandra, Jean-Francois Laslier, and William S. Zwicker

Published in: Dagstuhl Seminar Proceedings, Volume 10101, Computational Foundations of Social Choice (2010)

Abstract
From March 7 to March 12, 2010, the Dagstuhl Seminar 10101 ``Computational Foundations of Social Choice '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Felix Brandt, Vincent Conitzer, Lane A. Hemaspaandra, Jean-Francois Laslier, and William S. Zwicker. 10101 Abstracts Collection – Computational Foundations of Social Choice. In Computational Foundations of Social Choice. Dagstuhl Seminar Proceedings, Volume 10101, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{brandt_et_al:DagSemProc.10101.1,
  author =	{Brandt, Felix and Conitzer, Vincent and Hemaspaandra, Lane A. and Laslier, Jean-Francois and Zwicker, William S.},
  title =	{{10101 Abstracts Collection – Computational Foundations of Social Choice}},
  booktitle =	{Computational Foundations of Social Choice},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10101},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10101.1},
  URN =		{urn:nbn:de:0030-drops-25644},
  doi =		{10.4230/DagSemProc.10101.1},
  annote =	{Keywords: Social Choice Theory, Voting, Fair Division, Algorithms, Computational Complexity, Multiagent Systems}
}
Document
DOI: 10.4230/DagSemProc.10101.2
10101 Executive Summary – Computational Foundations of Social Choice

Authors: Felix Brandt, Vincent Conitzer, Lane A. Hemaspaandra, Jean-Francois Laslier, and William S. Zwicker

Published in: Dagstuhl Seminar Proceedings, Volume 10101, Computational Foundations of Social Choice (2010)

Abstract
This seminar addressed some of the key issues in computational social choice, a novel interdisciplinary field of study at the interface of social choice theory and computer science. Computational social choice is concerned with the application of computational techniques to the study of social choice mechanisms, such as voting rules and fair division protocols, as well as with the integration of social choice paradigms into computing. The seminar brought together many of the most active researchers in the field and focussed the research community currently forming around these important and exciting topics.
Cite as

Felix Brandt, Vincent Conitzer, Lane A. Hemaspaandra, Jean-Francois Laslier, and William S. Zwicker. 10101 Executive Summary – Computational Foundations of Social Choice. In Computational Foundations of Social Choice. Dagstuhl Seminar Proceedings, Volume 10101, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{brandt_et_al:DagSemProc.10101.2,
  author =	{Brandt, Felix and Conitzer, Vincent and Hemaspaandra, Lane A. and Laslier, Jean-Francois and Zwicker, William S.},
  title =	{{10101 Executive Summary – Computational Foundations of Social Choice}},
  booktitle =	{Computational Foundations of Social Choice},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10101},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10101.2},
  URN =		{urn:nbn:de:0030-drops-25637},
  doi =		{10.4230/DagSemProc.10101.2},
  annote =	{Keywords: Social Choice Theory, Voting, Fair Division, Algorithms, Computational Complexity, Multiagent Systems}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact